package com.sicheng.lc.周赛.分类.图论;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/26 21:42
 */
public class 从树中删除边的最小分数 {
    //https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/
    int t;
    int[] sum, in, out;
    List<Integer>[] g;
    int[] nums;

    public int minimumScore(int[] nums, int[][] edges) {
        init(nums, edges);
        dfs(0, -1);
        for (int[] edge : edges) {
            if (!isParent(edge[0], edge[1])) {
                swap(edge);
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < edges.length - 1; i++) {
            int x1 = edges[i][0], y1 = edges[i][1];
            for (int j = i + 1; j < edges.length; j++) {
                int x2 = edges[j][0], y2 = edges[j][1];
                int x, y, z;
                if (isParent(y1, x2)) {
                    y = sum[y2];
                    z = sum[y1] ^ y;
                    x = sum[0] ^ sum[y1];
                } else if (isParent(y2, x1)) {
                    y = sum[y1];
                    z = sum[y2] ^ y;
                    x = sum[0] ^ sum[y2];
                } else {
                    y = sum[y1];
                    x = sum[y2];
                    z = sum[0] ^ x ^ y;
                }
                res = min(res, max(x, y, z) - min(x, y, z));
            }
        }
        return res;
    }

    int max(int... x) {
        int max = x[0];
        for (int i = 1; i < x.length; i++) {
            max = Math.max(max, x[i]);
        }
        return max;
    }

    int min(int... x) {
        int min = x[0];
        for (int i = 1; i < x.length; i++) {
            min = Math.min(min, x[i]);
        }
        return min;
    }

    void swap(int[] nums) {
        int t = nums[0];
        nums[0] = nums[1];
        nums[1] = t;
    }

    private void init(int[] nums, int[][] edges) {
        sum = new int[nums.length];
        in = new int[nums.length];
        out = new int[nums.length];
        this.nums = nums;
        g = new ArrayList[nums.length];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
    }

    boolean isParent(int a, int b) {
        return in[b] >= in[a] && in[b] <= out[a];
    }

    public void dfs(int x, int pa) {
        in[x] = ++t;
        sum[x] = nums[x];
        for (int k : g[x]) {
            if (pa != k) {
                dfs(k, x);
                sum[x] ^= sum[k];
            }
        }
        out[x] = t;
    }
}
